#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <iostream>

using namespace std;

#define HEIGHT 9
#define WIDTH 18 

int POS[] = {1 << 0, 1 << 1, 1 << 2, 1 << 3};
int REV[] = {1, 0, 3, 2};

int maze[HEIGHT][WIDTH];

void
random_permutation (int *a)
{
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 4; j++) {
			if (rand () % 2) {
				swap (a[i], a[j]);
			}
		}
	}
}

void
dfs (int i, int j)
{
	pair<int,int> pos[] = {make_pair (i-1, j), make_pair (i+1, j), 
		make_pair (i, j-1), make_pair (i, j+1)};
	
	int ind[] = {0, 1, 2, 3};
	random_permutation (ind);
	
	for (int k = 0; k < 4; k++) {
		if (pos[ind[k]].first <= 0 || pos[ind[k]].first >= HEIGHT 
			|| pos[ind[k]].second < 0 || pos[ind[k]].second >= WIDTH 
			|| maze[pos[ind[k]].first][pos[ind[k]].second]) {
			continue;
		}
		
		maze[i][j] |= POS[ind[k]];
		maze[pos[ind[k]].first][pos[ind[k]].second] |= POS[REV[ind[k]]];
		
		dfs (pos[ind[k]].first, pos[ind[k]].second);
	}
}

int
main (int argc, char *argv[])
{
	int num = argc > 1 ? atoi (argv[1]) : 0;
	srand ((unsigned) time (0));
	
	while (num--)
	{
		for (int i = 0; i < HEIGHT; i++) {
			for (int j = 0; j < WIDTH; j++) {
				maze[i][j] = 0;
			}
		}
	
		//dfs (rand () % HEIGHT, rand () % WIDTH);
		dfs (0, 0);
		maze[0][0] |= POS[0] | POS[1];
		
		for (int i = 0; i < HEIGHT; i++)
		{
			for (int j = 0; j < WIDTH; j++)
			{
				if (j) {
					cout << " ";
				}
				cout << maze[i][j];
			}
			cout << endl;
		}
		cout << endl;
	}
	
	return EXIT_SUCCESS;
}
